class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // 状态表示 - 截止到 i 位置的连续子数组的最大和
        int[] dp = new int[n];
        // 初始化
        dp[0] = nums[0];
        // 状态转移方程
        for(int i = 1; i < n; i++){
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        }
        int ret = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }
}